package linear_list.leetcode.easy;

import java.util.HashSet;
import java.util.Set;

/**
 * @author Stark
 * @description 给你一个链表的头节点 head ，判断链表中是否有环
 * 题目链接：https://leetcode-cn.com/problems/linked-list-cycle
 * @date 2022/4/9 15:24
 **/
public class Num141_HasCycle {
    int choice = 1;
    public boolean hasCycle(ListNode head) {
        if(choice == 1) {
            //快慢指针法
            //快指针比慢指针每次都多走一步，在环里面相当于二者距离每次缩小1，总会相遇
            //要么在第一次追上的时候相遇,或者在第二次遇到是相遇,因为每次距离会减一
            //第一次没相遇说明他们之间的距离为1
            //因为两次追上的时候内必然会遇到,所以快指针走的距离最多为两倍环状结点数
            //那么慢指针在环里最多走环状结点数,
            //循环次数就是慢指针走的距离,所以时间复杂度为O(n)
            if (head == null || head.next == null)
                return false;
            ListNode cur = head, next = head;
            while (true) {
                if (head == null || next.next == null)
                    return false;
                next = next.next.next;
                cur = cur.next;
                if (next == cur)
                    return true;
            }
        }else if(choice == 2){
            //使用set集合判断
            if(head == null || head.next == null)
                return false;
            Set<ListNode> set = new HashSet<>();
            ListNode cur = head;
            while(cur != null){
                if(!set.add(cur))
                    return true;
                cur = cur.next;
            }
            return false;
        }
        return false;
    }
}
